package com.lovi.horseChess;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

import static com.lovi.horseChess.Test01.printChessBoard;

public class Test02 {
    public static void main(String[] args) {
//        个人思路：递归+回溯
//
//        1. 首先构建棋盘，我们规定需要走的位置格子为0，走过的位置为step
        int[][] chessBoard = new int[6][6];
//        2. 马儿在当前点把当前能往下的走的点都收集到list集合中list getStepList(int x,int y,int[][] chessBoard)
//        3. findStep(int x,int y , int step ,int[][] chessBoard )
//        for (int i = 0; i < 6; i++) {
//            for (int j = 0; j < 6; j++) {
//                chessBoard = new int[6][6];
//                excute(i, j, chessBoard);
//            }
//        }
        excute(5, 4, chessBoard);//80秒,160秒,111秒，126秒
        //尝试增加一个post判断 114秒，111秒 没什么区别
        /*
         天啊，
         当(2,5)的时候耗时128秒
         (5,4)耗时=80秒
         排序完成直接0秒
         */


    }

    public static ArrayList<Post> getStepList(int x, int y, int[][] chessBoard) {
        ArrayList<Post> list = new ArrayList<>();
        int[] newXArray = {x - 1, x + 1, x - 2, x + 2, x - 2, x + 2, x - 1, x + 1};
        int[] newYArray = {y - 2, y - 2, y - 1, y - 1, y + 1, y + 1, y + 2, y + 2};
        for (int i = 0; i < 8; i++) {
            int newX = newXArray[i], newY = newYArray[i];
            //边界条件
            if (0 <= newX && newX <= chessBoard.length - 1 && 0 <= newY && newY <= chessBoard[0].length - 1) {
                //并且，这个坐标在棋盘中是0【说明没加入到最终路径里】
                if (chessBoard[newX][newY] == 0) {
                    Post post = new Post();
                    post.setX(newX);
                    post.setY(newY);
                    list.add(post);
                }
            }
        }
        return list;
    }

    public static boolean findStep(int x, int y, int step, int[][] chessBoard) {
        chessBoard[x][y] = step;
        //        1. 当马儿进入当前点的时候先判断step是否为64，是就返回true
        //        2. 然后立刻标注step！（因为马儿确实走到了这个点）
        if (step == 36) {
            return true;
        }
        //        3. 查找当前点（x,y）的newList
        ArrayList<Post> newList = getStepList(x, y, chessBoard);

        //增加newList的排序
        sort(newList,chessBoard);
        //        1. newList只查找棋盘中没有访问过的（标注为0）
        if (newList.isEmpty()) {
            //5. 如果newList为empty，则先标注当前点为0（即未访问），然后返回false，进入回溯
            chessBoard[x][y] = 0;
            return false;
        } else {
//            4. 如果newList是有值，则遍历newList，进入递归findStep（nextX,nextY,step+1,chessBoard）;
//                    1. if(findStep){ xxx}如果递归结果为true，就return true即可。否则进入下一轮遍历
            for (Post post : newList) {
                //进入递归
                if (findStep(post.getX(), post.getY(), step + 1, chessBoard)) {
                    return true;
                }
            }
            //当前点全部遍历完了都没有找到，先设置当前step没有加入路径，返回false，进入回溯
            chessBoard[x][y] = 0;
            return false;
        }

    }

    public static void sort(ArrayList<Post> list,int[][] chessBoard){
        list.sort(new Comparator<Post>() {
            @Override
            public int compare(Post o1, Post o2) {
                //升序排序，从小到大
                return getStepList(o1.getX(),o1.getY(),chessBoard).size()
                        - getStepList(o2.getX(),o2.getY(),chessBoard).size();
            }
        });
    }

    public static void excute(int i, int j, int[][] chessBoard) {
        long start = System.currentTimeMillis();
        if (findStep(i, j, 1, chessBoard)) {
            System.out.println("(" + i + "," + j + ")" + "✅✅✅✅✅成功找到，打印如下✅✅✅✅✅");
            printChessBoard(chessBoard);
        } else {
            System.out.println("(" + i + "," + j + ")" + "❌❌❌❌❌找不到,打印如下❌❌❌❌❌");
            printChessBoard(chessBoard);
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时=" + (end - start) / 1000 + "秒");
        System.out.println("================================");
    }

}
